package 剑指offer;

/**
 * @author: tyy 剑指 Offer
 * 240. 搜索二维矩阵 II
    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。
 * @create: 2021-10-25 17:40
 * @description:
 **/
public class Solution9 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = 0;
        int n = matrix[0].length - 1;
        while (m < matrix.length && n >= 0) {
            if (matrix[m][n] == target) {
                return true;
            } else if (matrix[m][n] > target) {
                n--;
            } else {
                m++;
            }
        }
        return false;
    }
    public boolean searchMatrix2(int[][] m, int t) {
        int l = m.length;
        int w = m[0].length;
        int i=0;
        if(t>m[l-1][w-1]||t<m[0][0]) return false;
        while(w-1>=0&&i<=l-1){
            if(t<m[i][w-1]){
                w--;
                continue;
            }
            if(t==m[i][w-1]) return true;
            if(t>m[i][w-1]){
                i++;
            }
        }
        return false;
    }
    public boolean searchMatrix3(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = matrix[0].length - 1; j >= 0; j--) {
                if(target < matrix[i][j])continue;
                else if(target  == matrix[i][j]) return true;
                else break;
            }
        }
        return false;
    }
    public static void main(String[] args) {
//        int[] ints = new Solution9().searchMatrix(num);
//        System.out.println("ints = " + Arrays.toString(ints));
    }
}

